package offer;

/**
 * @author cyt
 * @create 2020-08-20 14:59
 */
public class JZ26 {
    private static TreeNode pre;

    /**
     * 未通过 100% 数据
     *
     * @param args
     */
    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);

        treeNode3.left = treeNode2;
        treeNode2.left = treeNode1;
        treeNode3.right = treeNode4;
        treeNode4.right = treeNode5;

        TreeNode convert = Convert(treeNode3);

        System.out.println(convert.toString());
    }

    /**
     * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     * <p>
     * 要求不能创建任何新的结点，只能调整树中结点指针的指向。
     */
    public static TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null) {
            return pRootOfTree;
        }
        TreeNode head = pRootOfTree;
        /**
         * 找到表头
         */
        while (head != null && head.right != null) {
            head = head.left;
        }
        inorder(pRootOfTree);
        return head;
    }

    static void inorder(TreeNode root) {
        if (root == null) {
            return;
        }
        inorder(root.left);
        /******中序部分*****/
        // 使用当前节点的left去指向上一个访问的节点，不能用right，因为它还未访问
        root.left = pre;
        if (pre != null)
        // 同理，之前访问过的节点的left已经被用了，因此用right
        {
            pre.left = root;
        }
        pre = root;
        inorder(root.right);
    }


}
